home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / fax / src / iv / InterViews / regexp.c++ < prev    next >
C/C++ Source or Header  |  1994-08-01  |  30KB  |  1,204 lines
  1. /*
  2.  * Copyright (c) 1987, 1988, 1989, 1990, 1991 Stanford University
  3.  * Copyright (c) 1991 Silicon Graphics, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute, and sell this software and 
  6.  * its documentation for any purpose is hereby granted without fee, provided
  7.  * that (i) the above copyright notices and this permission notice appear in
  8.  * all copies of the software and related documentation, and (ii) the names of
  9.  * Stanford and Silicon Graphics may not be used in any advertising or
  10.  * publicity relating to the software without the specific, prior written
  11.  * permission of Stanford and Silicon Graphics.
  12.  * 
  13.  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
  14.  * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
  15.  * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
  16.  *
  17.  * IN NO EVENT SHALL STANFORD OR SILICON GRAPHICS BE LIABLE FOR
  18.  * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
  19.  * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  20.  * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF 
  21.  * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE 
  22.  * OF THIS SOFTWARE.
  23.  */
  24.  
  25. /*
  26.  * Regexp - regular expression searching
  27.  */
  28.  
  29. #include <InterViews/regexp.h>
  30. #include <stdio.h>
  31. #include <string.h>
  32.  
  33. /*
  34.  * This version is based on the Henry Spencers public domain reimplementation
  35.  * of the regular expression matching subroutines.  They are included as
  36.  * static subroutines after the externally accessible routines.
  37.  */
  38.  
  39. /*
  40.  * Forward declarations for regcomp()'s friends.
  41.  */
  42. static regexp* regcomp(char* exp);
  43. static char* reg(int paren, int* flagp);
  44. static char* regbranch(int* flagp);
  45. static char* regpiece(int* flagp);
  46. static char* regatom(int* flagp);
  47. static char* regnode(char op);
  48. static char* regnext(register char* p);
  49. static void regc(char b);
  50. static void reginsert(char op, char* opnd);
  51. static void regtail(char* p, char* val);
  52. static void regoptail(char* p, char* val);
  53. static void regerror(char* s);
  54. static int regexec(register regexp* prog, register char* string);
  55. static int regtry(regexp* prog, char* string);
  56. static int regmatch(char* prog);
  57. static int regrepeat(char* p);
  58.  
  59.  
  60. inline char *
  61. FindNewline(char* s) {
  62.     return strchr(s, '\n');
  63. }
  64.  
  65. inline char *
  66. NextLine(char* s) {
  67.     char* newstart;
  68.  
  69.     if ((newstart = FindNewline(s)) != nil)
  70.     newstart++;
  71.     return newstart;
  72. }
  73.  
  74. Regexp::Regexp (const char* pat) {
  75.     int length = strlen(pat);
  76.     _pattern = new char[length+1];
  77.     strncpy(_pattern, pat, length);
  78.     _pattern[length] = '\0';
  79.     c_pattern = nil;
  80. }
  81.  
  82. Regexp::Regexp (const char* pat, int length) {
  83.     _pattern = new char[length+1];
  84.     strncpy(_pattern, pat, length);
  85.     _pattern[length] = '\0';
  86.     c_pattern = nil;
  87. }
  88.  
  89. Regexp::~Regexp () {
  90.     delete _pattern;
  91.     delete c_pattern;
  92. }
  93.  
  94. const char* Regexp::pattern() const { return _pattern; }
  95.  
  96. int Regexp::Search (const char* text, int length, int index, int range) {
  97.     boolean forwardSearch;
  98.     boolean frontAnchored;
  99.     boolean endAnchored;
  100.     char* searchStart;
  101.     char* searchLimit;
  102.     char* endOfLine = nil;
  103.     char* lastMatch = nil;
  104.     char csave;
  105.  
  106.     /*
  107.      * A small sanity check.  Otherwise length is unused in this function.
  108.      * This is really what the logic embedded in the old version of this
  109.      * routine enforced.
  110.      */
  111.     if (index + range > length) {
  112.     range = length - index;
  113.     if (range < 0)
  114.         return -1;
  115.     }
  116.  
  117.     if (c_pattern)
  118.     delete c_pattern;
  119.  
  120.     if ((c_pattern = regcomp(_pattern)) == nil)
  121.     return -1;
  122.  
  123.     c_pattern->startp[0] = nil;
  124.  
  125.     if (range < 0) {
  126.     forwardSearch = false;
  127.     searchLimit = (char *) text + index;
  128.     searchStart = (char *) searchLimit + range; /* range is negative */
  129.     } else {
  130.     forwardSearch = true;
  131.     searchStart = (char *) text + index;
  132.     searchLimit = (char *) searchStart + range;
  133.     }
  134.  
  135.     /* Mark end of text string so search will stop */
  136.     char save = *searchLimit;
  137.     *searchLimit = '\0';
  138.  
  139.     frontAnchored = _pattern[0] == '^';
  140.     endAnchored = _pattern[strlen(_pattern)-1] == '$';
  141.     if (frontAnchored && (searchStart != text || searchStart[-1] == '\n')) {
  142.     searchStart = NextLine(searchStart);
  143.     }
  144.  
  145.     while (searchStart && searchStart < searchLimit) {
  146.     int result;
  147.  
  148.     if (endAnchored && (endOfLine = FindNewline(searchStart)) != nil) {
  149.         csave = *endOfLine;
  150.         *endOfLine = '\0';
  151.     }
  152.  
  153.     result = regexec(c_pattern, searchStart);
  154.  
  155.     if (endOfLine)
  156.         *endOfLine = csave;
  157.  
  158.     if (result) {
  159.         /* Found a match */
  160.         if (forwardSearch)
  161.         break;  /* Done */
  162.         else {
  163.         lastMatch = c_pattern->startp[0];
  164.         searchStart = c_pattern->endp[0];
  165.         if (frontAnchored)
  166.             searchStart = NextLine(searchStart);
  167.         continue;
  168.         }
  169.     }
  170.     /* Did not find a match */
  171.     if (frontAnchored || endAnchored)
  172.         searchStart = NextLine(searchStart);
  173.     else
  174.         break;
  175.     }
  176.  
  177.     if (!forwardSearch && lastMatch) {
  178.     if (endAnchored && (endOfLine = FindNewline(lastMatch)) != nil) {
  179.         csave = *endOfLine;
  180.         *endOfLine = '\0';
  181.     }
  182.     (void) regexec(c_pattern, lastMatch); /* Refill startp and endp */
  183.     if (endOfLine)
  184.         *endOfLine = csave;
  185.     }
  186.  
  187.     *searchLimit = save;
  188.     c_pattern->textStart = (char *) text;
  189.  
  190.     return c_pattern->startp[0] - c_pattern->textStart;
  191. }
  192.  
  193. int Regexp::Match (const char* text, int length, int index) {
  194.  
  195.     if (c_pattern)
  196.     delete c_pattern;
  197.  
  198.     if ((c_pattern = regcomp(_pattern)) == nil)
  199.     return -1;
  200.  
  201.     c_pattern->startp[0] = nil;
  202.  
  203.     char save = *(text+length);
  204.     *(char*)(text+length) = '\0';
  205.  
  206.     c_pattern->textStart = (char *) text;
  207.     (void) regexec(c_pattern, (char *) text + index);
  208.  
  209.     *(char*)(text+length) = save;
  210.  
  211.     if (c_pattern->startp[0] != nil)
  212.         return c_pattern->endp[0] - c_pattern->startp[0];
  213.     else
  214.         return -1;
  215. }
  216.  
  217. int Regexp::BeginningOfMatch (int subexp) {
  218.     if (subexp < 0 || subexp > NSUBEXP ||
  219.         c_pattern == nil || c_pattern->startp[0] == nil)
  220.     return -1;
  221.     return c_pattern->startp[subexp] - c_pattern->textStart;
  222. }
  223.  
  224. int Regexp::EndOfMatch (int subexp) {
  225.     if (subexp < 0 || subexp > NSUBEXP ||
  226.         c_pattern == nil || c_pattern->startp[0] == nil)
  227.     return -1;
  228.     return c_pattern->endp[subexp] - c_pattern->textStart;
  229. }
  230.  
  231. /*
  232.  * regcomp and regexec
  233.  *
  234.  *    Copyright (c) 1986 by University of Toronto.
  235.  *    Written by Henry Spencer.  Not derived from licensed software.
  236.  *
  237.  *    Permission is granted to anyone to use this software for any
  238.  *    purpose on any computer system, and to redistribute it freely,
  239.  *    subject to the following restrictions:
  240.  *
  241.  *    1. The author is not responsible for the consequences of use of
  242.  *        this software, no matter how awful, even if they arise
  243.  *        from defects in it.
  244.  *
  245.  *    2. The origin of this software must not be misrepresented, either
  246.  *        by explicit claim or by omission.
  247.  *
  248.  *    3. Altered versions must be plainly marked as such, and must not
  249.  *        be misrepresented as being the original software.
  250.  *
  251.  * Beware that some of this code is subtly aware of the way operator
  252.  * precedence is structured in regular expressions.  Serious changes in
  253.  * regular-expression syntax might require a total rethink.
  254.  */
  255.  
  256. /*
  257.  * The "internal use only" fields in regexp.h are present to pass info from
  258.  * compile to execute that permits the execute phase to run lots faster on
  259.  * simple cases.  They are:
  260.  *
  261.  * regstart    char that must begin a match; '\0' if none obvious
  262.  * reganch    is the match anchored (at beginning-of-line only)?
  263.  * regmust    string (pointer into program) that match must include, or nil
  264.  * regmlen    length of regmust string
  265.  *
  266.  * Regstart and reganch permit very fast decisions on suitable starting points
  267.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  268.  * of lines that cannot possibly match.  The regmust tests are costly enough
  269.  * that regcomp() supplies a regmust only if the r.e. contains something
  270.  * potentially expensive (at present, the only such thing detected is * or +
  271.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  272.  * supplied because the test in regexec() needs it and regcomp() is computing
  273.  * it anyway.
  274.  */
  275.  
  276. /*
  277.  * Structure for regexp "program".  This is essentially a linear encoding
  278.  * of a nondeterministic finite-state machine (aka syntax charts or
  279.  * "railroad normal form" in parsing technology).  Each node is an opcode
  280.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  281.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  282.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  283.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  284.  * opposed to a collection of them) is never concatenated with anything
  285.  * because of operator precedence.)  The operand of some types of node is
  286.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  287.  * particular, the operand of a BRANCH node is the first node of the branch.
  288.  * (NB this is *not* a tree structure:  the tail of the branch connects
  289.  * to the thing following the set of BRANCHes.)  The opcodes are:
  290.  */
  291.  
  292. /* definition    number    opnd?    meaning */
  293. #define    END    0    /* no    End of program. */
  294. #define    BOL    1    /* no    Match "" at beginning of line. */
  295. #define    EOL    2    /* no    Match "" at end of line. */
  296. #define    ANY    3    /* no    Match any one character. */
  297. #define    ANYOF    4    /* str    Match any character in this string. */
  298. #define    ANYBUT    5    /* str    Match any character not in this string. */
  299. #define    BRANCH    6    /* node    Match this alternative, or the next... */
  300. #define    BACK    7    /* no    Match "", "next" ptr points backward. */
  301. #define    EXACTLY    8    /* str    Match this string. */
  302. #define    NOTHING    9    /* no    Match empty string. */
  303. #define    STAR    10    /* node    Match this (simple) thing 0 or more times. */
  304. #define    PLUS    11    /* node    Match this (simple) thing 1 or more times. */
  305. #define    OPEN    20    /* no    Mark this point in input as start of #n. */
  306.             /*    OPEN+1 is number 1, etc. */
  307. #define    CLOSE    30    /* no    Analogous to OPEN. */
  308.  
  309. /*
  310.  * Opcode notes:
  311.  *
  312.  * BRANCH    The set of branches constituting a single choice are hooked
  313.  *        together with their "next" pointers, since precedence prevents
  314.  *        anything being concatenated to any individual branch.  The
  315.  *        "next" pointer of the last BRANCH in a choice points to the
  316.  *        thing following the whole choice.  This is also where the
  317.  *        final "next" pointer of each individual branch points; each
  318.  *        branch starts with the operand node of a BRANCH node.
  319.  *
  320.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  321.  *        exists to make loop structures possible.
  322.  *
  323.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  324.  *        BRANCH structures using BACK.  Simple cases (one character
  325.  *        per match) are implemented with STAR and PLUS for speed
  326.  *        and to minimize recursive plunges.
  327.  *
  328.  * OPEN,CLOSE    ...are numbered at compile time.
  329.  */
  330.  
  331. /*
  332.  * A node is one char of opcode followed by two chars of "next" pointer.
  333.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  334.  * value is a positive offset from the opcode of the node containing it.
  335.  * An operand, if any, simply follows the node.  (Note that much of the
  336.  * code generation knows about this implicit relationship.)
  337.  *
  338.  * Using two bytes for the "next" pointer is vast overkill for most things,
  339.  * but allows patterns to get big without disasters.
  340.  */
  341. #define    OP(p)    (*(p))
  342. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  343. #define    OPERAND(p)    ((p) + 3)
  344.  
  345. /*
  346.  * Utility definitions.
  347.  */
  348. #ifndef RE_CHARBITS
  349. #define RE_CHARBITS    0xff
  350. #endif
  351.  
  352. #define    UCHARAT(p)    ((int)*(p)&RE_CHARBITS)
  353.  
  354. #define    FAIL(m)    { regerror(m); return(nil); }
  355. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  356. #define    META    "^$.[()|?+*\\"
  357.  
  358. /*
  359.  * Flags to be passed up and down.
  360.  */
  361. #define    HASWIDTH    01    /* Known never to match null string. */
  362. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  363. #define    SPSTART        04    /* Starts with * or +. */
  364. #define    WORST        0    /* Worst case. */
  365.  
  366. /*
  367.  * Global work variables for regcomp().
  368.  */
  369. static char *regparse;        /* Input-scan pointer. */
  370. static int regnpar;        /* () count. */
  371. static char regdummy;
  372. static char *regcode;        /* Code-emit pointer; ®dummy = don't. */
  373. static long regsize;        /* Code size. */
  374.  
  375. /*
  376.  - regcomp - compile a regular expression into internal code
  377.  *
  378.  * We can't allocate space until we know how big the compiled form will be,
  379.  * but we can't compile it (and thus know how big it is) until we've got a
  380.  * place to put the code.  So we cheat:  we compile it twice, once with code
  381.  * generation turned off and size counting turned on, and once "for real".
  382.  * This also means that we don't allocate space until we are sure that the
  383.  * thing really will compile successfully, and we never have to move the
  384.  * code and thus invalidate pointers into it.  (Note that it has to be in
  385.  * one piece because free() must be able to free it all.)
  386.  *
  387.  * Beware that the optimization-preparation code in here knows about some
  388.  * of the structure of the compiled regexp.
  389.  */
  390. static regexp *
  391. regcomp(char* exp) {
  392.     register regexp *r;
  393.     register char *scan;
  394.     register char *longest;
  395.     register int len;
  396.     int flags;
  397.  
  398.     if (exp == nil)
  399.         FAIL("nil argument");
  400.  
  401.     /* First pass: determine size, legality. */
  402.     regparse = exp;
  403.     regnpar = 1;
  404.     regsize = 0L;
  405.     regcode = ®dummy;
  406.     regc(REGEXP_MAGIC);
  407.     if (reg(0, &flags) == nil)
  408.         return(nil);
  409.  
  410.     /* Small enough for pointer-storage convention? */
  411.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  412.         FAIL("regexp too big");
  413.  
  414.     /* Allocate space. */
  415.     r = (regexp *) new char[sizeof(regexp) + (unsigned)regsize];
  416.  
  417.     /* Second pass: emit code. */
  418.     regparse = exp;
  419.     regnpar = 1;
  420.     regcode = r->program;
  421.     regc(REGEXP_MAGIC);
  422.     if (reg(0, &flags) == nil)
  423.         return(nil);
  424.  
  425.     /* Dig out information for optimizations. */
  426.     r->regstart = '\0';    /* Worst-case defaults. */
  427.     r->reganch = 0;
  428.     r->regmust = nil;
  429.     r->regmlen = 0;
  430.     scan = r->program+1;            /* First BRANCH. */
  431.     if (OP(regnext(scan)) == END) {        /* Only one top-level choice. */
  432.         scan = OPERAND(scan);
  433.  
  434.         /* Starting-point info. */
  435.         if (OP(scan) == EXACTLY)
  436.             r->regstart = *OPERAND(scan);
  437.         else if (OP(scan) == BOL)
  438.             r->reganch++;
  439.  
  440.         /*
  441.          * If there's something expensive in the r.e., find the
  442.          * longest literal string that must appear and make it the
  443.          * regmust.  Resolve ties in favor of later strings, since
  444.          * the regstart check works with the beginning of the r.e.
  445.          * and avoiding duplication strengthens checking.  Not a
  446.          * strong reason, but sufficient in the absence of others.
  447.          */
  448.         if (flags&SPSTART) {
  449.             longest = nil;
  450.             len = 0;
  451.             for (; scan != nil; scan = regnext(scan))
  452.                 if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  453.                     longest = OPERAND(scan);
  454.                     len = strlen(OPERAND(scan));
  455.                 }
  456.             r->regmust = longest;
  457.             r->regmlen = len;
  458.         }
  459.     }
  460.  
  461.     return(r);
  462. }
  463.  
  464. /*
  465.  - reg - regular expression, i.e. main body or parenthesized thing
  466.  *
  467.  * Caller must absorb opening parenthesis.
  468.  *
  469.  * Combining parenthesis handling with the base level of regular expression
  470.  * is a trifle forced, but the need to tie the tails of the branches to what
  471.  * follows makes it hard to avoid.
  472.  */
  473. static char *
  474. reg(int paren, int* flagp) {
  475.     register char *ret;
  476.     register char *br;
  477.     register char *ender;
  478.     register int parno;
  479.     int flags;
  480.  
  481.     *flagp = HASWIDTH;    /* Tentatively. */
  482.  
  483.     /* Make an OPEN node, if parenthesized. */
  484.     if (paren) {
  485.         if (regnpar >= NSUBEXP)
  486.             FAIL("too many ()");
  487.         parno = regnpar;
  488.         regnpar++;
  489.         ret = regnode(OPEN+parno);
  490.     } else
  491.         ret = nil;
  492.  
  493.     /* Pick up the branches, linking them together. */
  494.     br = regbranch(&flags);
  495.     if (br == nil)
  496.         return(nil);
  497.     if (ret != nil)
  498.         regtail(ret, br);    /* OPEN -> first. */
  499.     else
  500.         ret = br;
  501.     if (!(flags&HASWIDTH))
  502.         *flagp &= ~HASWIDTH;
  503.     *flagp |= flags&SPSTART;
  504.     while (*regparse == '|') {
  505.         regparse++;
  506.         br = regbranch(&flags);
  507.         if (br == nil)
  508.             return(nil);
  509.         regtail(ret, br);    /* BRANCH -> BRANCH. */
  510.         if (!(flags&HASWIDTH))
  511.             *flagp &= ~HASWIDTH;
  512.         *flagp |= flags&SPSTART;
  513.     }
  514.  
  515.     /* Make a closing node, and hook it on the end. */
  516.     ender = regnode((paren) ? CLOSE+parno : END);    
  517.     regtail(ret, ender);
  518.  
  519.     /* Hook the tails of the branches to the closing node. */
  520.     for (br = ret; br != nil; br = regnext(br))
  521.         regoptail(br, ender);
  522.  
  523.     /* Check for proper termination. */
  524.     if (paren && *regparse++ != ')') {
  525.         FAIL("unmatched ()");
  526.     } else if (!paren && *regparse != '\0') {
  527.         if (*regparse == ')') {
  528.             FAIL("unmatched ()");
  529.         } else
  530.             FAIL("junk on end");    /* "Can't happen". */
  531.         /* NOTREACHED */
  532.     }
  533.  
  534.     return(ret);
  535. }
  536.  
  537. /*
  538.  - regbranch - one alternative of an | operator
  539.  *
  540.  * Implements the concatenation operator.
  541.  */
  542. static char *
  543. regbranch(int* flagp) {
  544.     register char *ret;
  545.     register char *chain;
  546.     register char *latest;
  547.     int flags;
  548.  
  549.     *flagp = WORST;        /* Tentatively. */
  550.  
  551.     ret = regnode(BRANCH);
  552.     chain = nil;
  553.     while (*regparse != '\0' && *regparse != '|') {
  554.         if (*regparse == '\\' && regparse[1] == ')') {
  555.             regparse++;
  556.             break;
  557.         }
  558.         latest = regpiece(&flags);
  559.         if (latest == nil)
  560.             return(nil);
  561.         *flagp |= flags&HASWIDTH;
  562.         if (chain == nil)    /* First piece. */
  563.             *flagp |= flags&SPSTART;
  564.         else
  565.             regtail(chain, latest);
  566.         chain = latest;
  567.     }
  568.     if (chain == nil)    /* Loop ran zero times. */
  569.         (void) regnode(NOTHING);
  570.  
  571.     return(ret);
  572. }
  573.  
  574. /*
  575.  - regpiece - something followed by possible [*+?]
  576.  *
  577.  * Note that the branching code sequences used for ? and the general cases
  578.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  579.  * both the endmarker for their branch list and the body of the last branch.
  580.  * It might seem that this node could be dispensed with entirely, but the
  581.  * endmarker role is not redundant.
  582.  */
  583. static char *
  584. regpiece(int* flagp) {
  585.     register char *ret;
  586.     register char op;
  587.     register char *next;
  588.     int flags;
  589.  
  590.     ret = regatom(&flags);
  591.     if (ret == nil)
  592.         return(nil);
  593.  
  594.     op = *regparse;
  595.     if (!ISMULT(op)) {
  596.         *flagp = flags;
  597.         return(ret);
  598.     }
  599.  
  600.     if (!(flags&HASWIDTH) && op != '?')
  601.         FAIL("*+ operand could be empty");
  602.     *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  603.  
  604.     if (op == '*' && (flags&SIMPLE))
  605.         reginsert(STAR, ret);
  606.     else if (op == '*') {
  607.         /* Emit x* as (x&|), where & means "self". */
  608.         reginsert(BRANCH, ret);            /* Either x */
  609.         regoptail(ret, regnode(BACK));        /* and loop */
  610.         regoptail(ret, ret);            /* back */
  611.         regtail(ret, regnode(BRANCH));        /* or */
  612.         regtail(ret, regnode(NOTHING));        /* null. */
  613.     } else if (op == '+' && (flags&SIMPLE))
  614.         reginsert(PLUS, ret);
  615.     else if (op == '+') {
  616.         /* Emit x+ as x(&|), where & means "self". */
  617.         next = regnode(BRANCH);            /* Either */
  618.         regtail(ret, next);
  619.         regtail(regnode(BACK), ret);        /* loop back */
  620.         regtail(next, regnode(BRANCH));        /* or */
  621.         regtail(ret, regnode(NOTHING));        /* null. */
  622.     } else if (op == '?') {
  623.         /* Emit x? as (x|) */
  624.         reginsert(BRANCH, ret);            /* Either x */
  625.         regtail(ret, regnode(BRANCH));        /* or */
  626.         next = regnode(NOTHING);        /* null. */
  627.         regtail(ret, next);
  628.         regoptail(ret, next);
  629.     }
  630.     regparse++;
  631.     if (ISMULT(*regparse))
  632.         FAIL("nested *?+");
  633.  
  634.     return(ret);
  635. }
  636.  
  637. /*
  638.  - regatom - the lowest level
  639.  *
  640.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  641.  * it can turn them into a single node, which is smaller to store and
  642.  * faster to run.  Backslashed characters are exceptions, each becoming a
  643.  * separate node; the code is simpler that way and it's not worth fixing.
  644.  */
  645. static char *
  646. regatom(int* flagp) {
  647.     register char *ret;
  648.     int flags;
  649.  
  650.     *flagp = WORST;        /* Tentatively. */
  651.  
  652.     switch (*regparse++) {
  653.     case '^':
  654.         ret = regnode(BOL);
  655.         break;
  656.     case '$':
  657.         ret = regnode(EOL);
  658.         break;
  659.     case '.':
  660.         ret = regnode(ANY);
  661.         *flagp |= HASWIDTH|SIMPLE;
  662.         break;
  663.     case '[': {
  664.             register int classbeg;
  665.             register int classend;
  666.  
  667.             if (*regparse == '^') {    /* Complement of range. */
  668.                 ret = regnode(ANYBUT);
  669.                 regparse++;
  670.             } else
  671.                 ret = regnode(ANYOF);
  672.             if (*regparse == ']' || *regparse == '-')
  673.                 regc(*regparse++);
  674.             while (*regparse != '\0' && *regparse != ']') {
  675.                 if (*regparse == '-') {
  676.                     regparse++;
  677.                     if (*regparse == ']' || *regparse == '\0')
  678.                         regc('-');
  679.                     else {
  680.                         classbeg = UCHARAT(regparse-2)+1;
  681.                         classend = UCHARAT(regparse);
  682.                         if (classbeg > classend+1)
  683.                             FAIL("invalid [] range");
  684.                         for (; classbeg <= classend; classbeg++)
  685.                             regc(classbeg);
  686.                         regparse++;
  687.                     }
  688.                 } else
  689.                     regc(*regparse++);
  690.             }
  691.             regc('\0');
  692.             if (*regparse != ']')
  693.                 FAIL("unmatched []");
  694.             regparse++;
  695.             *flagp |= HASWIDTH|SIMPLE;
  696.         }
  697.         break;
  698.     case '\0':
  699.     case '|':
  700.         FAIL("internal urp");    /* Supposed to be caught earlier. */
  701.         break;
  702.     case '?':
  703.     case '+':
  704.     case '*':
  705.         FAIL("?+* follows nothing");
  706.         break;
  707.     case '\\':
  708.         if (*regparse == '\0')
  709.             FAIL("trailing \\");
  710.         if (*regparse == '(') {
  711.             regparse++;
  712.             ret = reg(1, &flags);
  713.             if (ret == nil)
  714.                 return(nil);
  715.             *flagp |= flags&(HASWIDTH|SPSTART);
  716.         } else {
  717.             ret = regnode(EXACTLY);
  718.             regc(*regparse++);
  719.             regc('\0');
  720.             *flagp |= HASWIDTH|SIMPLE;
  721.         }
  722.         break;
  723.     default: {
  724.             register int len;
  725.             register char ender;
  726.  
  727.             regparse--;
  728.             len = strcspn(regparse, META);
  729.             if (len <= 0)
  730.                 FAIL("internal disaster");
  731.             ender = *(regparse+len);
  732.             if (len > 1 && ISMULT(ender))
  733.                 len--;        /* Back off clear of ?+* operand. */
  734.             *flagp |= HASWIDTH;
  735.             if (len == 1)
  736.                 *flagp |= SIMPLE;
  737.             ret = regnode(EXACTLY);
  738.             while (len > 0) {
  739.                 regc(*regparse++);
  740.                 len--;
  741.             }
  742.             regc('\0');
  743.         }
  744.         break;
  745.     }
  746.  
  747.     return(ret);
  748. }
  749.  
  750. /*
  751.  - regnode - emit a node
  752.  */
  753. static char *            /* Location. */
  754. regnode(char op) {
  755.     register char *ret;
  756.     register char *ptr;
  757.  
  758.     ret = regcode;
  759.     if (ret == ®dummy) {
  760.         regsize += 3;
  761.         return(ret);
  762.     }
  763.  
  764.     ptr = ret;
  765.     *ptr++ = op;
  766.     *ptr++ = '\0';        /* Null "next" pointer. */
  767.     *ptr++ = '\0';
  768.     regcode = ptr;
  769.  
  770.     return(ret);
  771. }
  772.  
  773. /*
  774.  - regc - emit (if appropriate) a byte of code
  775.  */
  776. static void
  777. regc(char b) {
  778.     if (regcode != ®dummy)
  779.         *regcode++ = b;
  780.     else
  781.         regsize++;
  782. }
  783.  
  784. /*
  785.  - reginsert - insert an operator in front of already-emitted operand
  786.  *
  787.  * Means relocating the operand.
  788.  */
  789. static void
  790. reginsert(char op, char* opnd) {
  791.     register char *src;
  792.     register char *dst;
  793.     register char *place;
  794.  
  795.     if (regcode == ®dummy) {
  796.         regsize += 3;
  797.         return;
  798.     }
  799.  
  800.     src = regcode;
  801.     regcode += 3;
  802.     dst = regcode;
  803.     while (src > opnd)
  804.         *--dst = *--src;
  805.  
  806.     place = opnd;        /* Op node, where operand used to be. */
  807.     *place++ = op;
  808.     *place++ = '\0';
  809.     *place++ = '\0';
  810. }
  811.  
  812. /*
  813.  - regtail - set the next-pointer at the end of a node chain
  814.  */
  815. static void
  816. regtail(char* p, char* val) {
  817.     register char *scan;
  818.     register char *temp;
  819.     register int offset;
  820.  
  821.     if (p == ®dummy)
  822.         return;
  823.  
  824.     /* Find last node. */
  825.     scan = p;
  826.     for (;;) {
  827.         temp = regnext(scan);
  828.         if (temp == nil)
  829.             break;
  830.         scan = temp;
  831.     }
  832.  
  833.     if (OP(scan) == BACK)
  834.         offset = scan - val;
  835.     else
  836.         offset = val - scan;
  837.     *(scan+1) = (offset>>8)&0377;
  838.     *(scan+2) = offset&0377;
  839. }
  840.  
  841. /*
  842.  - regoptail - regtail on operand of first argument; nop if operandless
  843.  */
  844. static void
  845. regoptail(char* p, char* val) {
  846.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  847.     if (p == nil || p == ®dummy || OP(p) != BRANCH)
  848.         return;
  849.     regtail(OPERAND(p), val);
  850. }
  851.  
  852. /*
  853.  * regexec and friends
  854.  */
  855.  
  856. /*
  857.  * Global work variables for regexec().
  858.  */
  859. static char *reginput;        /* String-input pointer. */
  860. static char *regbol;        /* Beginning of input, for ^ check. */
  861. static char **regstartp;    /* Pointer to startp array. */
  862. static char **regendp;        /* Ditto for endp. */
  863.  
  864. /*
  865.  - regexec - match a regexp against a string
  866.  */
  867. static int
  868. regexec(register regexp* prog, register char* string) {
  869.     register char *s;
  870.  
  871.     /* Be paranoid... */
  872.     if (prog == nil || string == nil) {
  873.         regerror("nil parameter");
  874.         return(0);
  875.     }
  876.  
  877.     /* Check validity of program. */
  878.     if (UCHARAT(prog->program) != REGEXP_MAGIC) {
  879.         regerror("corrupted program");
  880.         return(0);
  881.     }
  882.  
  883.     /* If there is a "must appear" string, look for it. */
  884.     if (prog->regmust != nil) {
  885.         s = string;
  886.         while ((s = strchr(s, prog->regmust[0])) != nil) {
  887.             if (strncmp(s, prog->regmust, prog->regmlen) == 0)
  888.                 break;    /* Found it. */
  889.             s++;
  890.         }
  891.         if (s == nil)    /* Not present. */
  892.             return(0);
  893.     }
  894.  
  895.     /* Mark beginning of line for ^ . */
  896.     regbol = string;
  897.  
  898.     /* Simplest case:  anchored match need be tried only once. */
  899.     if (prog->reganch)
  900.         return(regtry(prog, string));
  901.  
  902.     /* Messy cases:  unanchored match. */
  903.     s = string;
  904.     if (prog->regstart != '\0')
  905.         /* We know what char it must start with. */
  906.         while ((s = strchr(s, prog->regstart)) != nil) {
  907.             if (regtry(prog, s))
  908.                 return(1);
  909.             s++;
  910.         }
  911.     else
  912.         /* We don't -- general case. */
  913.         do {
  914.             if (regtry(prog, s))
  915.                 return(1);
  916.         } while (*s++ != '\0');
  917.  
  918.     /* Failure. */
  919.     return(0);
  920. }
  921.  
  922. /*
  923.  - regtry - try match at specific point
  924.  */
  925. static int            /* 0 failure, 1 success */
  926. regtry(regexp* prog, char* string) {
  927.     register int i;
  928.     register char **sp;
  929.     register char **ep;
  930.  
  931.     reginput = string;
  932.     regstartp = prog->startp;
  933.     regendp = prog->endp;
  934.  
  935.     sp = prog->startp;
  936.     ep = prog->endp;
  937.     for (i = NSUBEXP; i > 0; i--) {
  938.         *sp++ = nil;
  939.         *ep++ = nil;
  940.     }
  941.     if (regmatch(prog->program + 1)) {
  942.         prog->startp[0] = string;
  943.         prog->endp[0] = reginput;
  944.         return(1);
  945.     } else
  946.         return(0);
  947. }
  948.  
  949. /*
  950.  - regmatch - main matching routine
  951.  *
  952.  * Conceptually the strategy is simple:  check to see whether the current
  953.  * node matches, call self recursively to see whether the rest matches,
  954.  * and then act accordingly.  In practice we make some effort to avoid
  955.  * recursion, in particular by going through "ordinary" nodes (that don't
  956.  * need to know whether the rest of the match failed) by a loop instead of
  957.  * by recursion.
  958.  */
  959. static int            /* 0 failure, 1 success */
  960. regmatch(char* prog) {
  961.     register char *scan;    /* Current node. */
  962.     char *next;        /* Next node. */
  963.  
  964.     scan = prog;
  965.     while (scan != nil) {
  966.         next = regnext(scan);
  967.  
  968.         switch (OP(scan)) {
  969.         case BOL:
  970.             if (reginput != regbol)
  971.                 return(0);
  972.             break;
  973.         case EOL:
  974.             if (*reginput != '\0')
  975.                 return(0);
  976.             break;
  977.         case ANY:
  978.             if (*reginput == '\0')
  979.                 return(0);
  980.             reginput++;
  981.             break;
  982.         case EXACTLY: {
  983.                 register int len;
  984.                 register char *opnd;
  985.  
  986.                 opnd = OPERAND(scan);
  987.                 /* Inline the first character, for speed. */
  988.                 if (*opnd != *reginput)
  989.                     return(0);
  990.                 len = strlen(opnd);
  991.                 if (len > 1 && strncmp(opnd, reginput, len) != 0)
  992.                     return(0);
  993.                 reginput += len;
  994.             }
  995.             break;
  996.         case ANYOF:
  997.             if (*reginput == '\0')
  998.                 return(0);
  999.             if (strchr(OPERAND(scan), *reginput) == nil)
  1000.                 return(0);
  1001.             reginput++;
  1002.             break;
  1003.         case ANYBUT:
  1004.             if (*reginput == '\0')
  1005.                 return(0);
  1006.             if (strchr(OPERAND(scan), *reginput) != nil)
  1007.                 return(0);
  1008.             reginput++;
  1009.             break;
  1010.         case NOTHING:
  1011.             break;
  1012.         case BACK:
  1013.             break;
  1014.         case OPEN+1:
  1015.         case OPEN+2:
  1016.         case OPEN+3:
  1017.         case OPEN+4:
  1018.         case OPEN+5:
  1019.         case OPEN+6:
  1020.         case OPEN+7:
  1021.         case OPEN+8:
  1022.         case OPEN+9: {
  1023.                 register int no;
  1024.                 register char *save;
  1025.  
  1026.                 no = OP(scan) - OPEN;
  1027.                 save = reginput;
  1028.  
  1029.                 if (regmatch(next)) {
  1030.                     /*
  1031.                      * Don't set startp if some later
  1032.                      * invocation of the same parentheses
  1033.                      * already has.
  1034.                      */
  1035.                     if (regstartp[no] == nil)
  1036.                         regstartp[no] = save;
  1037.                     return(1);
  1038.                 } else
  1039.                     return(0);
  1040.             }
  1041.             break;
  1042.         case CLOSE+1:
  1043.         case CLOSE+2:
  1044.         case CLOSE+3:
  1045.         case CLOSE+4:
  1046.         case CLOSE+5:
  1047.         case CLOSE+6:
  1048.         case CLOSE+7:
  1049.         case CLOSE+8:
  1050.         case CLOSE+9: {
  1051.                 register int no;
  1052.                 register char *save;
  1053.  
  1054.                 no = OP(scan) - CLOSE;
  1055.                 save = reginput;
  1056.  
  1057.                 if (regmatch(next)) {
  1058.                     /*
  1059.                      * Don't set endp if some later
  1060.                      * invocation of the same parentheses
  1061.                      * already has.
  1062.                      */
  1063.                     if (regendp[no] == nil)
  1064.                         regendp[no] = save;
  1065.                     return(1);
  1066.                 } else
  1067.                     return(0);
  1068.             }
  1069.             break;
  1070.         case BRANCH: {
  1071.                 register char *save;
  1072.  
  1073.                 if (OP(next) != BRANCH)        /* No choice. */
  1074.                     next = OPERAND(scan);    /* Avoid recursion. */
  1075.                 else {
  1076.                     do {
  1077.                         save = reginput;
  1078.                         if (regmatch(OPERAND(scan)))
  1079.                             return(1);
  1080.                         reginput = save;
  1081.                         scan = regnext(scan);
  1082.                     } while (scan != nil && OP(scan) == BRANCH);
  1083.                     return(0);
  1084.                     /* NOTREACHED */
  1085.                 }
  1086.             }
  1087.             break;
  1088.         case STAR:
  1089.         case PLUS: {
  1090.                 register char nextch;
  1091.                 register int no;
  1092.                 register char *save;
  1093.                 register int min;
  1094.  
  1095.                 /*
  1096.                  * Lookahead to avoid useless match attempts
  1097.                  * when we know what character comes next.
  1098.                  */
  1099.                 nextch = '\0';
  1100.                 if (OP(next) == EXACTLY)
  1101.                     nextch = *OPERAND(next);
  1102.                 min = (OP(scan) == STAR) ? 0 : 1;
  1103.                 save = reginput;
  1104.                 no = regrepeat(OPERAND(scan));
  1105.                 while (no >= min) {
  1106.                     /* If it could work, try it. */
  1107.                     if (nextch == '\0' || *reginput == nextch)
  1108.                         if (regmatch(next))
  1109.                             return(1);
  1110.                     /* Couldn't or didn't -- back up. */
  1111.                     no--;
  1112.                     reginput = save + no;
  1113.                 }
  1114.                 return(0);
  1115.             }
  1116.             break;
  1117.         case END:
  1118.             return(1);    /* Success! */
  1119.         default:
  1120.             regerror("memory corruption");
  1121.             return(0);
  1122.         }
  1123.  
  1124.         scan = next;
  1125.     }
  1126.  
  1127.     /*
  1128.      * We get here only if there's trouble -- normally "case END" is
  1129.      * the terminating point.
  1130.      */
  1131.     regerror("corrupted pointers");
  1132.     return(0);
  1133. }
  1134.  
  1135. /*
  1136.  - regrepeat - repeatedly match something simple, report how many
  1137.  */
  1138. static int
  1139. regrepeat(char* p) {
  1140.     register int count = 0;
  1141.     register char *scan;
  1142.     register char *opnd;
  1143.  
  1144.     scan = reginput;
  1145.     opnd = OPERAND(p);
  1146.     switch (OP(p)) {
  1147.     case ANY:
  1148.         count = strlen(scan);
  1149.         scan += count;
  1150.         break;
  1151.     case EXACTLY:
  1152.         while (*opnd == *scan) {
  1153.             count++;
  1154.             scan++;
  1155.         }
  1156.         break;
  1157.     case ANYOF:
  1158.         while (*scan != '\0' && strchr(opnd, *scan) != nil) {
  1159.             count++;
  1160.             scan++;
  1161.         }
  1162.         break;
  1163.     case ANYBUT:
  1164.         while (*scan != '\0' && strchr(opnd, *scan) == nil) {
  1165.             count++;
  1166.             scan++;
  1167.         }
  1168.         break;
  1169.     default:        /* Oh dear.  Called inappropriately. */
  1170.         regerror("internal foulup");
  1171.         count = 0;    /* Best compromise. */
  1172.         break;
  1173.     }
  1174.     reginput = scan;
  1175.  
  1176.     return(count);
  1177. }
  1178.  
  1179. /*
  1180.  - regnext - dig the "next" pointer out of a node
  1181.  */
  1182. static char *
  1183. regnext(register char* p) {
  1184.     register int offset;
  1185.  
  1186.     if (p == ®dummy)
  1187.         return(nil);
  1188.  
  1189.     offset = NEXT(p);
  1190.     if (offset == 0)
  1191.         return(nil);
  1192.  
  1193.     if (OP(p) == BACK)
  1194.         return(p-offset);
  1195.     else
  1196.         return(p+offset);
  1197. }
  1198.  
  1199. static void
  1200. regerror(char* s) {
  1201.     fprintf(stderr, "regexp: %s\n", s);
  1202. }
  1203.  
  1204.